package com.hl.algor_data_struct.sort;

/**
 * Created by yuanhailong on 2021/10/24.
 * 插入排序：
 * 找到第一个元素，然后查看这个元素是否比前面的元素小，如果小就往前移动
 * 时间复杂度O(N^2)  插入排序如果在数据排序好的情况下优于冒泡和选择
 *
 * 例如 一个数组[1,2,3,4,5] 时间复杂度为O(N)
 *     而对于[5,4,3,2,1] 时间复杂度则为O(N^2)
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = SortConstants.sortArr;
        for(int i=1;i<arr.length;i++){
            //从I的前一个位置向前循坏移动
            //for(int j=i-1;j>=0 && arr[j]> arr[j+1];j--){
            for(int j=i-1;j>=0;j--){
                if(arr[j]> arr[j+1]) {
                    SortConstants.swap(arr, j, j + 1);
                }
            }
        }


        for(int num:arr){
            System.out.println(num);
        }


    }

}
